package madixin.t962;

import java.util.Stack;

class Solution {
    public int maxWidthRamp(int[] A) {
        if (A == null || A.length < 1) {
            return 0;
        }
        //单调递减栈
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < A.length; i++) {
            if (stack.isEmpty() || A[stack.peek()] > A[i]) {
                stack.push(i);
            }
        }
        int max = 0;
        for (int i = A.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && A[stack.peek()] <= A[i]) {
                max = Math.max(max, i - stack.pop());
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxWidthRamp(new int[]{6, 0, 8, 2, 1, 5}));
        System.out.println(s.maxWidthRamp(new int[]{9, 8, 1, 0, 1, 9, 4, 0, 4, 1}));
    }
}